1. Field of the Invention
The present invention generally relates to predicting traffic state on a transportation network. More specifically, for each link in the network, deviations from the historical traffic are stored in a matrix format and used for successive time period predictions.
2. Description of the Related Art
In the transportation sector, travel time information is necessary to provide route guidance and best path information to travelers and to fleet operators. This information is usually based on average travel time values for every road segment (link) in the transportation network. Using the average travel times, best path computations can be made, using any of a variety of shortest path algorithms. A route is thus a sequence of one or more links in the transportation network. In order to determine route guidance and best path information for future time periods, several conventional methods are available.
The standard way in which such information is provided is to make use of average values, as described above. The use of those average values provides an average-case best route or path to a user. However, due to congestion on roadways, average-case travel times on the link may vary considerably from the travel times at specific time periods. For example, the peak travel time along a link may be twice the travel time at off-peak periods. In such cases, it is desirable to make use of time-dependent values for the travel times on links in providing route guidance and/or best path information to users.
In a first conventional method related to reporting vehicle data, a method is proposed in which objects such as queues are identified in a traffic stream and those objects are tracked, allowing for an estimated value of the traffic parameter, which may include travel time. In particular, data “relating to the mean number of vehicles in the respective queue, the queue length, the mean waiting time in the queue and the mean number of vehicles on the respective direction lane set of a roadway section, and relating to current turn-off rates, can be used on a continuous basis for producing historical progress lines”, where historical progress lines imply the prediction of the current value to a present or near future time period. This method becomes quite complex if link interactions are taken into account and real-time computation of such values would not be possible.
Future road traffic state prediction is, however, the topic of a second conventional method. A method for predicting speed information is provided for multiple time intervals into the future (e.g., on the order of 0-60 minutes to several hours or 1-3 days into the future). The method described takes a historical speed for a similar link at the same time instant for the same type of day and multiplies it by a weighting factor less than or equal to one, determined through regression on such parameters as predicted weather conditions, construction, and any known scheduled events on the segment.
This method hence relies upon high-quality predicted weather data, as well as information on scheduled events along the link in question. However, such data is not often available in a form amenable to incorporation into traffic predictions.
However, to the present inventors, these methods described above suggest that a better solution is required in several instances.
(i) In the case where weather predictions and scheduled event data are not available, good predictions of future travel time are still often required.
(ii) It is not always sufficient to compute a single weighting factor to scale the average travel time (e.g., as proposed in the second conventional method), since the effects of the weather or an event can vary widely across different links. Additionally, the highly detailed data on present conditions, as is assumed in the first conventional method, is generally unavailable on most road segments, and is less valid for predictions beyond the very short-term.
Hence, a need exists for a better method of providing vehicular traffic prediction. Prior to the present invention, there has been no method that balances the need for more accurate predictions in the near-term with computational efficiency, so that the method is applicable to large traffic networks in real time.